Threaded Binary Tree and Morris Traversal

Motivation

对于有着空的左孩子右孩子指针的节点 内存被浪费了，所以在TBT里我们利用这些内存来储存一些地址

Transform a normal binary tree to TBT

1. 最左边最右边的空指针不改动
2. 将其他的空指针改为：

   • Left ptr = inorder predecessor 因为该节点没有inorder predecessor 中序遍历第一个节点
     

   • Right ptr = inorder successor 因为该节点没有inorder successor 中序遍历最后一个节点
     

我们可以在节点里加入两个flag来代表左指针右指针指向的是ancestor还是child
最后对于中序遍历的起点和终点的左右指针 连向dummy node flag设为ancestor

莫里斯遍历利用线段树的概念可以实现iterative inorder traversal of tree without using stack TIME O(N) SPACE O(1)
Pseudocode

Initialize current as root 
While current is not NULL
   If current does not has a left child
      a) access current's data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost 
         node in current's left subtree
      b) Go to that left child, i.e., current = current->left  (set current's left to be null)

LeetCode94: use above method to achieve inorder traversal

class Solution {
    public List<Integer> inorderTraversal(TreeNode node) {
        List<Integer> list = new ArrayList();

        while(node != null) {
            if(node.left == null) {
                list.add(node.val);
                node = node.right;
            }
            else {
                TreeNode nextNode = node.left;
                TreeNode p = node.left;
                while(p.right != null) p = p.right;
                p.right = node;//p:rightmost node in the leftsubtree
                node.left = null;
                node = nextNode;
            }
        }
        return list;
    }
}

打赏